Мультипредметная личная олимпиада ЮФУ

среди школьников 2016

А. Простая задача

Чему будет равен остаток от деления 2ⁿ на 10?

Вход. Единственное неотрицательное число n (0 ≤ n ≤ 10⁹).

Выход. Выведите остаток от деления 2ⁿ на 10.

Пример входа

4

Пример выхода

6

РЕШЕНИЕ

возведение в степень

Анализ алгоритма

В задаче следует вычислить 2ⁿ mod 10 за время O(log₂n).

Рассмотрим также математическое решение. Заметим, что 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32. Остаток от деления на 10 – это последняя цифра степени 2ⁿ, она повторяется: 2, 4, 8, 6. То есть

· если n % 4 == 1, то 2ⁿ mod 10 = 2,

· если n % 4 == 2, то 2ⁿ mod 10 = 4,

· если n % 4 == 3, то 2ⁿ mod 10 = 8,

· если n % 4 == 0, то 2ⁿ mod 10 = 6

Следует отдельно обработать случай n = 0, тогда 2⁰ mod 10 = 1.

Реализация алгоритма

#include <stdio.h>

__int64 n, res;

__int64 powmod(__int64 x, __int64 n, __int64 m)

{

if (n == 0) return 1;

if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

return (x * powmod(x, n - 1, m)) % m;

}

int main(void)

{

scanf("%I64d",&n);

res = powmod(2,n,10);

printf("%I64d\n",res);

return 0;

}

Реализация алгоритма – математическое решение

#include <stdio.h>

int n;

int main(void)

{

scanf("%d",&n);

if (n == 0) printf("1\n"); else

if (n % 4 == 1) printf("2\n"); else

if (n % 4 == 2) printf("4\n"); else

if (n % 4 == 3) printf("8\n"); else

printf("6\n");

return 0;

}